/*
 * @lc app=leetcode.cn id=19 lang=cpp
 *
 * [19] 删除链表的倒数第 N 个结点
 */
#include <stack>

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
  public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        using std::stack;
        stack<ListNode *> list_node;
        ListNode *new_head = nullptr;
        int index = 1;

        while (head) {
            list_node.push(head);
            head = head->next;
        }

        while (!list_node.empty()) {
            if (index != n) {
                list_node.top()->next = new_head;
                new_head = list_node.top();
            }
            list_node.pop();
            ++index;
        }

        return new_head;
    }
};
// @lc code=end
